################################################################################
# fscheme (C) Copyright funnyos@qq.com 2018
#
# This software is freely distributable under the terms of the MIT 
# License. See the file LICENSE for details.
################################################################################
.eqv    true             1
.eqv    invalid          -1
.eqv    word_size        4
.eqv    pair_size        12
.eqv    atom_size        12
.eqv    max_symbol_size  256
.eqv    max_string_size  1024
.eqv    type_nil         -1
.eqv    type_token       0x2000
.eqv    type_pair        0x0100
.eqv    type_string      0x0000
.eqv    type_symbol      0x0001
.eqv    type_boolean     0x0002
.eqv    type_integer     0x0003
.eqv    type_fraction    0x0004
.eqv    type_decimal     0x0005
.eqv    type_character   0x0006
.eqv    type_vector      0x0007
.data
zero:             .double 0.0
ten:              .double 10.0
one:              .double 1.0
minus_one:        .double -1.0
nil_string:       .asciiz "()"
lparen_string:    .asciiz "( "
rparen_string:    .asciiz " )"
dot_string:       .asciiz " . "
t_string:         .asciiz "#t"
f_string:         .asciiz "#f"
sexp:             .asciiz "( a ( b \"1 2 3\") \"123\"@03 sdf334 )"
err_msg:          .asciiz "Error!"
################################################################################
.text

.globl main

################################################################################
# main()
# entry point
################################################################################
main:
    la   $a0, sexp
    jal  parse_sexp
    beq  $v1, $zero, main.error
    move $a0, $v0
    jal  print_sexp
    j    exit
main.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>, int <v1>) parse_sexp(char* <a0>)
# parse s-expression, give string (char* <a0>), and return address (void* <v0>)
# args:
#   a0: s-expression string pointer
# returns:
#   v0: s-expression stored address pointer
#   v1: wether expression successfully ended
# note:
#   s5: -1, invalid
#   s6: contains nil value address
################################################################################
parse_sexp:
    addi $sp, $sp, -56
    sw   $ra, 52($sp)
    sw   $s6, 48($sp)
    sw   $s5, 44($sp)
    sw   $s4, 40($sp)
    sw   $s3, 36($sp)
    sw   $s2, 32($sp)
    sw   $s1, 28($sp)
    sw   $s0, 24($sp)
    sw   $t5, 20($sp)
    sw   $t4, 16($sp)
    sw   $t3, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    li   $a0, pair_size
    li   $v0, 9
    syscall
    li   $t1, type_nil
    sw   $t1, 0($v0)
    sw   $zero, 4($v0)
    sw   $zero, 8($v0)
    li   $s5, invalid   # invalid thing
    move $s6, $v0       # nil
    move $a0, $t0
    jal  read_list
    lbu  $t1, 0($v1)
    bne  $t1, $zero, parse_sexp.not_ended
    li   $v1, 1
    j    parse_sexp.exit
parse_sexp.not_ended:
    move $v1, $zero
parse_sexp.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $t3, 12($sp)
    lw   $t4, 16($sp)
    lw   $t5, 20($sp)
    lw   $s0, 24($sp)
    lw   $s1, 28($sp)
    lw   $s2, 32($sp)
    lw   $s3, 36($sp)
    lw   $s4, 40($sp)
    lw   $s5, 44($sp)
    lw   $s6, 48($sp)
    lw   $ra, 52($sp)
    addi $sp, $sp, 56
    jr $ra
################################################################################
# description:
# (char <s4>, char* <v1>, void* <v0>) token(char* <a0>)
# read token (char* <a0>) and store to address (void* <v0>)
# args:
#   a0: token pointer
# returns:
#   v0: token value address
#   s4: keyword char, or zero if not keyword
#   v1: new string pointer
################################################################################
token:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    jal  eat_whitespace
    lbu  $t1, 0($t0)
    bne  $t1, $zero, token.lparen
    move $s4, $zero
    j    token.exit
token.lparen:
    lbu  $t1, 0($t0)
    li   $t2, '('
    bne  $t1, $t2, token.rparen
    addi $t0, $t0, 1
    li   $s4, '('
    j    token.exit
token.rparen:
    lbu  $t1, 0($t0)
    li   $t2, ')'
    bne  $t1, $t2, token.dot
    addi $t0, $t0, 1
    li   $s4, ')'
    j    token.exit
token.dot:
    lbu  $t1, 0($t0)
    li   $t2, '.'
    bne  $t1, $t2, token.dquote
    addi $t0, $t0, 1
    li   $s4, '.'
    j    token.exit
token.dquote:
    lbu  $t1, 0($t0)
    li   $t2, '"'
    bne  $t1, $t2, token.other
    jal  read_literal
    j    token.exit
token.other:
    jal  read_non_literal
token.exit:
    move $v1, $t0
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
################################################################################
# description:
# (void* <v0>, char* <v1>) read_literal_once(char* <a0>)
# read literal (char* <a0>) once and store literal address to (void* <v0>)
# args:
#   a0: literal pointer
# returns:
#   v0: literal address
#   v1: new string pointer
################################################################################
read_literal_once:
    addi $sp, $sp, -24
    sw   $ra, 20($sp)
    sw   $s3, 16($sp)
    sw   $s2, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    jal  read_string
    move $t0, $v0
    move $s2, $v0
    move $v1, $zero
    lbu  $t1, 0($t0)
    li   $t2, '@'
    bne  $t2, $t1, read_literal_once.not_at
    addi $t0, $t0, 1
    lbu  $t1, 0($t0)
    move $a0, $t1
    jal  hex_value
    beq  $v0, $s5, read_literal_once.error
    sll  $v1, $v1, 4
    add  $v1, $v1, $v0
    addi $t0, $t0, 1
    lbu  $t1, 0($t0)
    move $a0, $t1
    jal  hex_value
    beq  $v0, $s5, read_literal_once.error
    sll  $v1, $v1, 4
    add  $v1, $v1, $v0
    addi $t0, $t0, 1
    move $a0, $s2
    move $a1, $v1
    jal  get_literal
    j    read_literal_once.exit
read_literal_once.not_at:
    move $a0, $t1
    jal  is_delimiter
    bne  $v0, $zero, read_literal_once.if_comma
    j    read_literal_once.cons_literal
read_literal_once.if_comma:
    li   $t2, ','
    bne  $t2, $t1, read_literal_once.error
read_literal_once.cons_literal:
    li   $a0, atom_size
    li   $v0, 9
    syscall
    sw   $v1, 0($v0)
    sw   $s2, 4($v0)  # $s2 contains string address
    sw   $s3, 8($v0)  # $s3 contains string length
read_literal_once.exit:
    move $v1, $t0
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $s2, 12($sp)
    lw   $s3, 16($sp)
    lw   $ra, 20($sp)
    addi $sp, $sp, 24
    jr $ra
read_literal_once.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>, char* <v1>) read_literal(char* <a0>)
# read literal (char* <a0>) and store literal address to (void* <v0>)
# args:
#   a0: literal pointer
# returns:
#   v0: literal address
#   v1: new string pointer
################################################################################
read_literal:
    addi $sp, $sp, -20
    sw   $ra, 16($sp)
    sw   $s3, 12($sp)
    sw   $s2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    jal  read_literal_once
    move $t0, $v0
    move $s2, $v0
    lbu  $t1, 0($t0)
    li   $t2, ','
    bne  $t2, $t1, read_literal.exit
    li   $a0, word_size
    li   $v0, 9
    syscall
    move $s1, $v0
    sw   $s2, 0($v0)
    move $t3, $zero
read_literal.loop:
    lbu  $t1, 0($t0)
    bne  $t2, $t1, read_literal.loop_exit
    move $a0, $t0
    jal  read_literal_once
    move $s2, $v0
    move $t1, $v1
    li   $a0, word_size
    li   $v0, 9
    syscall
    sw   $s2, 0($v0)
    addi $t3, $t3, 1
    j    read_literal.loop
read_literal.loop_exit:
    li   $a0, atom_size
    li   $v0, 9
    syscall
    li   $v1, type_vector
    sw   $v1, 0($v0)
    sw   $s1, 4($v0)  # $s1 contains vector address
    sw   $t3, 8($v0)  # $t3 contains vector length
read_literal.exit:
    move $s1, $v0
    move $a0, $t1
    jal  is_delimiter
    bne  $v0, $zero, read_literal_once.error
    move $v0, $s1
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $s2, 8($sp)
    lw   $s3, 12($sp)
    lw   $ra, 16($sp)
    addi $sp, $sp, 20
    jr $ra
read_literal.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>, char* <v1>, int <s1>) read_string(char* <a0>)
# read string (char* <a0>) and store string address to (char* <v0>)
# args:
#   a0: string pointer
# returns:
#   v0: string address
#   v1: new string pointer
#   s1: string length
################################################################################
read_string:
    addi $sp, $sp, -24
    sw   $ra, 20($sp)
    sw   $t4, 16($sp)
    sw   $t3, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    addi $t0, $t0, 1
    jal  literal_length
    move $s1, $v0
    addi $v0, $v0, 1
    move $a0, $v0
    li   $v0, 9
    syscall
    move $s2, $v0
    move $t2, $v0
    move $t1, $zero
read_string.loop:
    lbu  $t3, 0($t0)
    li   $t0, '"'
    beq  $t0, $t3, read_string.exit
    li   $t0, '\\'
    bne  $t0, $t3, read_string.eos
    addi $t0, $t0, 1
    li   $t0, 'n'
    bne  $t0, $t3, read_string.escape_tab
    li   $t0, '\n'
    sb   $t0, 0($t2)
    addi $t2, $t2, 1
read_string.escape_tab:
    li   $t0, 't'
    bne  $t0, $t3, read_string.escape_backslash
    li   $t0, '\t'
    sb   $t0, 0($t2)
    addi $t2, $t2, 1
read_string.escape_backslash:
    li   $t0, '\\'
    bne  $t0, $t3, read_string.escape_dquote
    # li   $t0, '\\'
    sb   $t0, 0($t2)
    addi $t2, $t2, 1
read_string.escape_dquote:
    li   $t0, '"'
    bne  $t0, $t3, read_string.eos
    # li   $t0, '"'
    sb   $t0, 0($t2)
    addi $t2, $t2, 1
read_string.eos:
    beq  $t0, $zero, read_string.error
    sb   $t3, 0($t2)
    addi $t0, $t0, 1
    addi $t2, $t2, 1
    addi $t1, $t1, 1
    li   $t4, max_string_size
    bne  $t1, $t4, read_string.loop
read_string.exit:
    sb   $zero, 0($t2)
    addi $t0, $t0, 1
    move $v0, $s2
    move $v1, $t0
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $t3, 12($sp)
    lw   $t4, 16($sp)
    lw   $ra, 20($sp)
    addi $sp, $sp, 24
    jr $ra
read_string.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# int <v0> literal_length(char* <a0>)
# get length of literal string
# args:
#   a0: the literal string
# returns:
#   v0: its length
################################################################################
literal_length:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $v0, $zero                   # initialize counter
    move $t0, $a0
    addi $t0, $t0, 1
literal_length.loop:
    lbu  $t1, ($t0)
    beq  $t1, $zero, literal_length.error
    li   $t2, '"'
    beq  $t1, $t2, literal_length.done
    li   $t2, '\\'
    bne  $t1, $t2, literal_length.inc
    addi $t0, $t0, 1
literal_length.inc:
    addi $v0, $v0, 1
    addi $t0, $t0, 1
    j    literal_length.loop
literal_length.done:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr    $ra
literal_length.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>) get_literal(char* <a0>, int <a1>)
# get literal (char* <a0>) with type (int <a1>)
# args:
#   a0: literal string pointer
#   a1: literal type
# returns:
#   v0: literal value
# s-expression storage:
# 1. nil
#           -1       |    nil    |    nil
# 2. pair
#           0x0100   |    car    |    cdr
# 3. atom
# 3.1 string
#           0x0000   | str addr  | str length
# 3.2 symbol
#           0x0001   | sym addr  | sym length
# 3.3 boolean
#           0x0002   | bool val  | 
# 3.4 integer
#           0x0003   | int  val  | 1
# 3.5 fraction
#           0x0004   | numer val | denom val 
# 3.6 decimal
#           0x0005   | double val| double val 
# 3.7 character
#           0x0006   | int  val  | 
# 3.8 vector
#           0x0007   | vec addr  | vec length
################################################################################
get_literal:
    addi $sp, $sp, -28
    sw   $ra, 24($sp)
    sw   $t2, 20($sp)
    sw   $t1, 16($sp)
    sw   $t0, 12($sp)
    sw   $s3, 8($sp)
    sw   $s2, 4($sp)
    sw   $s1, 0($sp)
    ### push stack ###
    bne  $a1, $zero, get_literal.get_symbol
    move $s2, $a0
    move $s3, $s1
get_literal.get_symbol:
    li   $t1, type_symbol
    bne  $a1, $t1, get_literal.get_boolean
    move $s2, $a0
    move $s3, $s1
    j    get_literal.exit
get_literal.get_boolean:
    li   $t1, type_boolean
    bne  $a1, $t1, get_literal.get_integer
    lbu  $t2, 0($a0)
    li   $t1, 't'
    bne  $t1, $t2, get_literal.get_boolean.false
    li   $s2, 1
    j    get_literal.get_boolean.done
get_literal.get_boolean.false:
    move $s2, $zero
get_literal.get_boolean.done:
    j    get_literal.exit
get_literal.get_integer:
    li   $t1, type_integer
    bne  $a1, $t1, get_literal.get_fraction
    jal  str_to_int
    move $s2, $v0
    li   $s3, 1
    j    get_literal.exit
get_literal.get_fraction:
    li   $t1, type_fraction
    bne  $a1, $t1, get_literal.get_decimal
    jal  str_to_fraction
    move $s2, $v0
    move $s3, $v1
    j    get_literal.exit
get_literal.get_decimal:
    li   $t1, type_decimal
    bne  $a1, $t1, get_literal.get_character
    jal  str_to_double
    mfc1.d  $s2, $f2
    j    get_literal.exit
get_literal.get_character:
    li   $t1, type_character
    bne  $a1, $t1, get_literal.error
    li   $t1, 1
    bne  $s3, $t1, get_literal.error
    lbu  $s2, 0($a0)
    j    get_literal.exit
get_literal.exit:
    move $s1, $a1
    li   $a0, atom_size
    li   $v0, 9
    syscall
    sw   $s1, 0($v0)
    sw   $s2, 4($v0)
    sw   $s3, 8($v0)
    ### pop stack ###
    lw   $s1, 0($sp)
    lw   $s2, 4($sp)
    lw   $s3, 8($sp)
    lw   $t0, 12($sp)
    lw   $t1, 16($sp)
    lw   $t2, 20($sp)
    lw   $ra, 24($sp)
    addi $sp, $sp, 28
    jr   $ra
get_literal.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# int <v0> non_literal_length(char* <a0>)
# get length of non-literal string
# args:
#   a0: the non-literal string
# returns:
#   v0: its length
################################################################################
non_literal_length:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t2, $zero                   # initialize counter
    move $t0, $a0
non_literal_length.loop:
    lbu  $t1, ($t0)
    beq  $t1, $zero, non_literal_length.error
    move $a0, $t1
    jal  is_delimiter
    bne  $v0, $zero, non_literal_length.done
    addi $t2, $t2, 1
    addi $t0, $t0, 1
    j    non_literal_length.loop
non_literal_length.done:
    addi $v0, $t2, 1
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr   $ra
non_literal_length.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>, char* <v1>) read_non_literal(char* <a0>)
# read non-literal (char* <a0>) and store literal address to (void* <v0>)
# args:
#   a0: non-literal pointer
# returns:
#   v0: non-literal address
#   v1: new string pointer
# note:
#   non-literal contains 
#   zero (equals '0')
#   unsigned-int (start with '1'-'9'),
#   hex-number (start with '0x')
#   operator (start with other character except '"')
################################################################################
read_non_literal:
    addi $sp, $sp, -36
    sw   $ra, 32($sp)
    sw   $s3, 28($sp)
    sw   $s2, 24($sp)
    sw   $s1, 20($sp)
    sw   $t4, 16($sp)
    sw   $t3, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t5, $a0
    jal  non_literal_length
    move $a0, $v0
    li   $v0, 9
    syscall
    move $t0, $v0
    move $t3, $t0
    li   $t1, max_symbol_size
read_non_literal.loop:
    lbu  $t4, 0($t5)
    move $a0, $t4
    jal  is_delimiter
    beq  $t4, $zero, read_non_literal.error
    bne  $v0, $zero, read_non_literal.done
    sb   $t4, 0($t0)
    addi $t5, $t5, 1
    addi $t0, $t0, 1
    addi $t1, $t1, -1
    bnez $t1, read_non_literal.loop
read_non_literal.done:
    sb   $zero, 0($t0)
    lbu  $t2, 0($t3)
    li   $t1, '0'
    beq  $t1, $t2, read_non_literal.enum
    li   $t1, '1'
    bltu $t2, $t1, read_non_literal.operator
    li   $t1, '9'
    bltu $t1, $t2, read_non_literal.operator
read_non_literal.int:
    move $a0, $t3
    jal  str_to_int
    li   $s1, type_integer
    move $s2, $v0
    li   $s3, 1
    j    read_non_literal.exit
read_non_literal.enum:
    addi $t3, $t3, 1
    lbu  $t2, 0($t3)
    move $a0, $t2
    jal  is_delimiter
    beq  $v0, $zero, read_non_literal.hex
    li   $s1, type_integer
    move $s2, $zero
    li   $s3, 1
    j    read_non_literal.exit
read_non_literal.hex:
    li   $t1, 'x'
    bne  $t1, $t2, read_non_literal.error
    addi $t3, $t3, 1
    move $a0, $t3
    jal  read_hex
    li   $s1, type_integer
    move $s2, $v0
    li   $s3, 1
    j    read_non_literal.exit
read_non_literal.operator:
    li   $s1, type_symbol
    move $s2, $t3
    sub  $s3, $t0, $t3
read_non_literal.exit:
    li   $a0, atom_size
    li   $v0, 9
    syscall
    sw   $s1, 0($v0)
    sw   $s2, 4($v0)
    sw   $s3, 8($v0)
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $t3, 12($sp)
    lw   $t4, 16($sp)
    lw   $s1, 20($sp)
    lw   $s2, 24($sp)
    lw   $s3, 28($sp)
    lw   $ra, 32($sp)
    addi $sp, $sp, 36
    jr $ra
read_non_literal.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (int <v0>) read_hex(char* <a0>)
# read hex (char* <a0>) and return hex value (int <v0>)
# args:
#   a0: hex string pointer
# returns:
#   v0: hex value
################################################################################
read_hex:
    addi $sp, $sp, -12
    sw   $ra, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $v1, $zero
read_hex.loop:
    lbu  $t0, 0($a0)
    move $t1, $a0
    move $a0, $t0
    jal  is_delimiter
    move $a0, $t1
    bne  $v0, $zero, read_hex.done
    move $a0, $t0
    jal  digit_value
    beq  $v0, $s5, read_hex.error
    move $t0, $v0
    sll  $v1, $v1, 4
    add  $v1, $v1, $t0
    addi $a0, $a0, 1
    j    read_hex.loop
read_hex.done:
    move $v1, $v0
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $ra, 8($sp)
    addi $sp, $sp, 12
    jr $ra
read_hex.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>, char* <v1>) read_list(char* <a0>)
# read list (char* <a0>) and store to address (void* <v0>)
# args:
#   a0: list pointer
# returns:
#   v0: result address
#   v1: new string pointer
################################################################################
read_list:
    addi $sp, $sp, -32
    sw   $ra, 28($sp)
    sw   $s3, 24($sp)
    sw   $s2, 20($sp)
    sw   $s1, 16($sp)
    sw   $t3, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t5, $a0
    jal  eat_whitespace
    move $a0, $v0
    jal  token
    move $t0, $s4
    li   $t1, type_token
    bne  $t0, $t1, read_list.error
    move $t0, $s5
    li   $t1, '('
    bne  $t0, $t1, read_list.error
    jal  is_next_rparen
    beq  $v0, $zero, read_list.not_nil
    addi $t5, $t5, 1
    move $v0, $s6
    j    read_list.exit
read_list.not_nil:
    jal  read_datum
    move $a0, $v0
    jal  single_list
    move $t2, $v0
    move $t3, $v0
read_list.loop:
    jal  eat_whitespace
    lbu  $t0, 0($t5)
    li   $t1, ')'
    beq  $t0, $t1, read_list.tail
    li   $t1, '.'
    beq  $t0, $t1, read_list.tail
    beq  $t0, $zero, read_list.error
    jal  read_datum
    move $a0, $v0
    jal  single_list
    sw   $v0, 8($t3)
    move $t3, $v0
    j    read_list.loop
read_list.tail:
    lbu  $t0, 0($t5)
    li   $t1, '.'
    bne  $t0, $t1, read_list.rparen
    addi $t5, $t5, 1
    jal  read_datum
    sw   $v0, 8($t3)
read_list.rparen:
    jal  token
    move $t0, $s4
    li   $t1, type_token
    bne  $t0, $t1, read_list.error
    move $t0, $s5
    li   $t1, ')'
    bne  $t0, $t1, read_list.error
    li   $s1, type_pair
    move $s2, $t2
    move $s3, $s6
    j    read_list.done
read_list.done:
    li   $a0, pair_size
    li   $v0, 9
    syscall
    move $t0, $v0
    sw   $s1, 0($t0)
    sw   $s2, 4($t0)
    sw   $s3, 8($t0)
    move $v0, $t0
    move $v1, $t5
read_list.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $t3, 12($sp)
    lw   $s1, 16($sp)
    lw   $s2, 20($sp)
    lw   $s3, 24($sp)
    lw   $ra, 28($sp)
    addi $sp, $sp, 32
    jr $ra
read_list.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (void* <v0>) read_datum(char* <a0>)
# read datum (char* <a0>) and store to address (void* <v0>)
# args:
#   a0: datum pointer
# returns:
#   v0: result address
#   v1: new string pointer
################################################################################
read_datum:
    addi $sp, $sp, -12
    sw   $ra, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t2, $a0
    jal  eat_whitespace
    lbu  $t0, 0($t2)
    li   $t1, '('
    bne  $t0, $t1, read_datum.atom
    jal  read_list
    j    read_datum.exit
read_datum.atom:
    li   $a0, atom_size
    li   $v0, 9
    syscall
    move $t0, $v0
    jal  token
    lw   $s1, 0($v0)
    lw   $s2, 4($v0)
    lw   $s3, 8($v0)
    sw   $s1, 0($t0)
    sw   $s2, 4($t0)
    sw   $s3, 8($t0)
    move $v0, $t0
    move $v1, $t2
read_datum.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $ra, 8($sp)
    addi $sp, $sp, 12
    jr $ra
################################################################################
# description:
# is_next_rparen()
################################################################################
is_next_rparen:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t2, $a0
    jal  eat_whitespace
    lbu  $t0, 0($a0)
    li   $t1, ')'
    bne  $t0, $t1, is_next_rparen.false
    li   $v0, 1
    j    is_next_rparen.exit
is_next_rparen.false:
    move $v0, $zero
is_next_rparen.exit:
    move $a0, $t2
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
################################################################################
# description:
# (void* <v0>) single_list(void* <a0>)
# create single list with item (void* <a0>) and store to address (void* <v0>)
# args:
#   a0: single list item
# returns:
#   v0: result address
################################################################################
single_list:
    addi $sp, $sp, -8
    sw   $ra, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    li   $a0, pair_size
    li   $v0, 9
    syscall
    sw   $t0, 4($v0)
    li   $t0, type_pair
    sw   $t0, 0($v0)
    move $t0, $s6
    sw   $t0, 8($v0)
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $ra, 4($sp)
    addi $sp, $sp, 8
    jr $ra
################################################################################
# description:
# print_sexp()
# s-expression storage:
# 1. nil
#              -1    |    nil    |    nil
# 2. pair
#           0x0100   |    car    |    cdr
# 3. atom
# 3.1 string
#           0x0000   | str addr  | str length
# 3.2 symbol
#           0x0001   | sym addr  | sym length
# 3.3 boolean
#           0x0002   | bool val  | 
# 3.4 integer
#           0x0003   | int  val  | 1
# 3.5 fraction
#           0x0004   | numer val | denom val 
# 3.6 decimal
#           0x0005   | double val| double val 
# 3.7 character
#           0x0006   | int  val  | 
# 3.8 vector
#           0x0007   | vec addr  | vec length
# note:
# type_of, car, cdr instructions are like follows:
#   lw   $v0, 0($a0)   #type_of
#   lw   $v0, 4($a0)   #car
#   lw   $v0, 8($a0)   #cdr
################################################################################
print_sexp:
    addi $sp, $sp, -28
    sw   $ra, 24($sp)
    sw   $t5, 20($sp)
    sw   $t4, 16($sp)
    sw   $t3, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    lw   $t0, 0($a0)
    lw   $t1, 4($a0)
    lw   $t2, 8($a0)
    li   $t3, type_nil
    bne  $t0, $t3, print_sexp.pair
    la   $a0, nil_string
    li   $v0, 4
    syscall
    j    print_sexp.exit
print_sexp.pair:
    move $t4, $a0
    li   $t3, type_pair
    bne  $t0, $t3, print_sexp.string
    la   $a0, lparen_string
    li   $v0, 4
    syscall
print_sexp.pair.loop:
    lw   $t0, 0($t4)
    lw   $t1, 4($t4)
    lw   $t2, 8($t4)
    li   $t3, type_pair
    bne  $t0, $t3, print_sexp.pair.loop_exit
    beq  $t2, $s6, print_sexp.pair.loop_exit
    bne  $t0, $t3, print_sexp.pair.print_self
    move $a0, $t1
    jal  print_sexp
    j    print_sexp.pair.print_if_dot
print_sexp.pair.print_self:
    move $a0, $t4
    jal  print_sexp
print_sexp.pair.print_if_dot:
    li   $t3, type_pair
    bne  $t0, $t3, print_sexp.pair.next
    lw   $t5, 0($t2)
    beq  $t5, $t3, print_sexp.pair.print_if_space
    la   $a0, dot_string
    li   $v0, 4
    syscall
    j    print_sexp.pair.next
print_sexp.pair.print_if_space:
    li   $a0, ' '
    li   $v0, 11
    syscall
print_sexp.pair.next:
    lw   $t4, 8($t4)
    j    print_sexp.pair.loop
print_sexp.pair.loop_exit:
    li   $t3, type_pair
    bne  $t0, $t3, print_sexp.pair.tail_print_self
    move $a0, $t1
    jal  print_sexp
    j    print_sexp.pair.tail_print
print_sexp.pair.tail_print_self:
    move $a0, $t4
    jal  print_sexp
print_sexp.pair.tail_print:
    la   $a0, rparen_string
    li   $v0, 4
    syscall
    j    print_sexp.exit
print_sexp.string:
    li   $t3, type_string
    bne  $t0, $t3, print_sexp.symbol
    li   $a0, '"'
    li   $v0, 11
    syscall
    move $a0, $t1
    li   $v0, 4
    syscall
    li   $a0, '"'
    li   $v0, 11
    syscall
    j    print_sexp.exit
print_sexp.symbol:
    li   $t3, type_symbol
    bne  $t0, $t3, print_sexp.boolean
    move $a0, $t1
    li   $v0, 4
    syscall
    j    print_sexp.exit
print_sexp.boolean:
    li   $t3, type_boolean
    bne  $t0, $t3, print_sexp.integer
    bne  $t1, $zero, print_sexp.true
    la   $a0, f_string
    li   $v0, 4
    syscall
    j    print_sexp.exit
print_sexp.true:
    la   $a0, t_string
    li   $v0, 4
    syscall
    j    print_sexp.exit
print_sexp.integer:
    li   $t3, type_integer
    bne  $t0, $t3, print_sexp.fraction
    move $a0, $t1
    li   $v0, 1
    syscall
    j    print_sexp.exit
print_sexp.fraction:
    li   $t3, type_fraction
    bne  $t0, $t3, print_sexp.decimal
    move $a0, $t1
    li   $v0, 1
    syscall
    li   $a0, '/'
    li   $v0, 11
    syscall
    move $a0, $t2
    li   $v0, 1
    syscall
    j    print_sexp.exit
print_sexp.decimal:
    li   $t3, type_decimal
    bne  $t0, $t3, print_sexp.character
    mtc1.d  $t1, $f12
    li   $v0, 3
    syscall
    j    print_sexp.exit
print_sexp.character:
    li   $t3, type_character
    bne  $t0, $t3, print_sexp.vector
    move $a0, $t1
    li   $v0, 11
    syscall
    j    print_sexp.exit
print_sexp.vector:
    li   $t3, type_vector
    bne  $t0, $t3, print_sexp.error
    li   $a0, '#'
    li   $v0, 11
    syscall
    la   $a0, lparen_string
    li   $v0, 4
    syscall
print_sexp.vector.loop:
    bleu $t2, $zero, print_sexp.vector.right
    move $a0, $t1
    jal  print_sexp
    addi $t2, $t2, -1
    j    print_sexp.vector.loop
print_sexp.vector.right:
    la   $a0, rparen_string
    li   $v0, 4
    syscall
print_sexp.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $t3, 12($sp)
    lw   $t4, 16($sp)
    lw   $t5, 20($sp)
    lw   $ra, 24($sp)
    addi $sp, $sp, 28
    jr $ra
print_sexp.error:
    la   $a0, err_msg
    j    error
################################################################################
# utils
################################################################################

################################################################################
# description:
# char* <v0> eat_whitespace(char* <a0>)
# advance the buffer pointer until it reaches the next non-whitespace char
# args:
#   a0: string pointer
# returns:
#   v0: pointer point to the next non-whitespace char
################################################################################
eat_whitespace:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    move $t1, $zero    # make sure that the upper half of $t1 is cleared
eat_whitespace.loop:
    lbu  $t1, 0($t0)   # get the character to be tested
    addi $t0, $t0, 1   # advance the buffer pointer
    beq  $t1, $zero, eat_whitespace.exit
    move $a0, $t1
    jal  is_space
    bne  $v0, $zero, eat_whitespace.loop
    li   $t2, ';'
    beq  $t1, $t2, eat_whitespace.eat_comments
    j    eat_whitespace.exit
eat_whitespace.eat_comments:
    move $a0, $t0
    jal  eat_comments
    move $t0, $v0
    j    eat_whitespace.loop
eat_whitespace.exit:
    addi $v0, $t0, -1  # set the return value to the current pointer
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
################################################################################
# description:
# char* <v0> eat_comments(char* <a0>)
# advance the buffer pointer until it reaches the next line
# args:
#   a0: string pointer
# returns:
#   v0: pointer point to the next line
################################################################################
eat_comments:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    move $t1, $zero
eat_comments.loop:
    lbu  $t1, 0($t0)   # get the character to be tested
    addi $t0, $t0, 1   # advance the buffer pointer
    beq  $t1, $zero, eat_comments.exit
    li   $t2, '\n'
    beq  $t1, $t2, eat_comments.exit
    j    eat_comments.loop
eat_comments.exit:
    addi $v0, $t0, -1  # set the return value to the current pointer
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
################################################################################
# description:
# int <v0> is_space(char <a0>)
# wether (char <a0>) is space
# args:
#   a0: char value
# returns:
#   v0: wether char is space
################################################################################
is_space:
    addi $sp, $sp, -8
    sw   $ra, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    li   $t0, ' '
    beq  $a0, $t0, is_space.true
    li   $t0, '\t'
    beq  $a0, $t0, is_space.true
    li   $t0, '\r'
    beq  $a0, $t0, is_space.true
    li   $t0, '\n'
    beq  $a0, $t0, is_space.true
    move $v0, $zero
    j    is_space.exit
is_space.true:
    li   $v0, true
is_space.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $ra, 4($sp)
    addi $sp, $sp, 8
    jr $ra
################################################################################
# description:
# is_delimiter()
################################################################################
is_delimiter:
    addi $sp, $sp, -8
    sw   $ra, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    beq  $a0, 0, is_delimiter.true
    li   $t0, ' '
    beq  $a0, $t0, is_delimiter.true
    li   $t0, '\t'
    beq  $a0, $t0, is_delimiter.true
    li   $t0, '\r'
    beq  $a0, $t0, is_delimiter.true
    li   $t0, '\n'
    beq  $a0, $t0, is_delimiter.true
    li   $t0, '('
    beq  $a0, $t0, is_delimiter.true
    li   $t0, ')'
    beq  $a0, $t0, is_delimiter.true
    li   $t0, '"'
    beq  $a0, $t0, is_delimiter.true
    li   $t0, ';'
    beq  $a0, $t0, is_delimiter.true
    li   $v0, 0
    j    is_delimiter.exit
is_delimiter.true:
    li   $v0, 1
is_delimiter.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $ra, 4($sp)
    addi $sp, $sp, 8
    jr $ra
################################################################################
# description:
# (int <v0>) hex_value(char <a0>)
# if <a0> in [0-9a-fA-F], return corresponding hex value, else return -1
# args:
#   a0: the char
# returns:
#   v0: hex value
################################################################################
hex_value:
    addi $sp, $sp, -12
    sw   $ra, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    li   $t1, '0'
    bltu $t0, $t1, hex_value.not_hex
    li   $t1, '9'
    bltu $t1, $t0, hex_value.maybe_hex_upper
    subi $t0, $t0, '0'
    j    hex_value.exit
hex_value.maybe_hex_upper:
    li   $t1, 'A'
    bltu $t0, $t1, hex_value.not_hex
    li   $t1, 'F'
    bltu $t1, $t0, hex_value.maybe_hex_lower
    subi $t0, $t0, 'A'
    addi $t0, $t0, 10
    j    hex_value.exit
hex_value.maybe_hex_lower:
    li   $t1, 'a'
    bltu $t0, $t1, hex_value.not_hex
    li   $t1, 'f'
    bltu $t1, $t0, hex_value.not_hex
    subi $t0, $t0, 'a'
    addi $t0, $t0, 10
    j    hex_value.exit
hex_value.not_hex:
    li   $t0, invalid
hex_value.exit:
    move $v0, $t0
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $ra, 8($sp)
    addi $sp, $sp, 12
    jr $ra
################################################################################
# description:
# (int <v0>) digit_value(char <a0>)
# if <a0> in [0-9], return corresponding digit value, else return -1
# args:
#   a0: the char
# returns:
#   v0: digit value
################################################################################
digit_value:
    addi $sp, $sp, -12
    sw   $ra, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $t0, $a0
    li   $t1, '0'
    bltu $t0, $t1, digit_value.not_digit
    li   $t1, '9'
    bltu $t1, $t0, digit_value.not_digit
    subi $t0, $t0, '0'
    j    digit_value.exit
digit_value.not_digit:
    li   $t0, invalid
digit_value.exit:
    move $v0, $t0
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $ra, 8($sp)
    addi $sp, $sp, 12
    jr $ra
################################################################################
# description:
# (int <v0>) str_to_int(char <a0>)
# parse string to int
# args:
#   a0: the string pointer
# returns:
#   v0: int value
################################################################################
str_to_int:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $v0, $zero
    lbu  $t0, 0($a0)
    li   $t1, '-'
    bne  $t0, $t1, str_to_int.positive
    li   $t2, 1
    addi $a0, $a0, 1
    j    str_to_int.calc
str_to_int.positive:
    move $t2, $zero
    li   $t1, '+'
    bne  $t0, $t1, str_to_int.calc
    addi $a0, $a0, 1
str_to_int.calc:
    lbu  $t0, 0($a0)
    beq  $t0, $zero, str_to_int.done
    li   $t1, '0'
    bltu $t0, $t1, str_to_int.error
    li   $t1, '9'
    bltu $t1, $t0, str_to_int.error
    subi $t0, $t0, '0'
    mul  $v0, $v0, 10
    add  $v0, $v0, $t0
    addi $a0, $a0, 1
    j    str_to_int.calc
str_to_int.done:
    beq  $t2, $zero, str_to_int.exit
    mul  $v0, $v0, -1    
str_to_int.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
str_to_int.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (int <v0>, int <v1>) str_to_fraction(char <a0>)
# parse string to fraction
# args:
#   a0: the string pointer
# returns:
#   v0: numerator value
#   v1: denominator value
################################################################################
str_to_fraction:
    addi $sp, $sp, -20
    sw   $ra, 16($sp)
    sw   $t3, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    move $v0, $zero
    move $v1, $zero
    move $t3, $zero
    lbu  $t0, 0($a0)
    li   $t1, '-'
    bne  $t0, $t1, str_to_fraction.positive
    li   $t2, 1
    addi $a0, $a0, 1
    j    str_to_fraction.calc
str_to_fraction.positive:
    move $t2, $zero
    li   $t1, '+'
    bne  $t0, $t1, str_to_fraction.calc
    addi $a0, $a0, 1
str_to_fraction.calc:
    lbu  $t0, 0($a0)
    beq  $t0, $zero, str_to_fraction.done
    li   $t1, '/'
    bne  $t0, $t1, str_to_fraction.not_slash
    li   $t3, 1
    addi $a0, $a0, 1
    j    str_to_fraction.calc
str_to_fraction.not_slash:
    li   $t1, '0'
    bltu $t0, $t1, str_to_fraction.error
    li   $t1, '9'
    bltu $t1, $t0, str_to_fraction.error
    subi $t0, $t0, '0'
    beq  $t3, $zero, str_to_fraction.other
    mul  $v1, $v1, 10
    add  $v1, $v1, $t0
    j    str_to_fraction.inc
str_to_fraction.other:
    mul  $v0, $v0, 10
    add  $v0, $v0, $t0
str_to_fraction.inc:
    addi $a0, $a0, 1
    j    str_to_fraction.calc
str_to_fraction.done:
    beq  $t3, $zero, str_to_fraction.error
    beq  $t2, $zero, str_to_fraction.exit
    mul  $v0, $v0, -1    
str_to_fraction.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $t3, 12($sp)
    lw   $ra, 16($sp)
    addi $sp, $sp, 20
    jr $ra
str_to_fraction.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# (double <v0, v1>) str_to_double(char <a0>)
# parse string to double value
# args:
#   a0: the string pointer
# returns:
#   v0, v1: double value
################################################################################
str_to_double:
    addi $sp, $sp, -16
    sw   $ra, 12($sp)
    sw   $t2, 8($sp)
    sw   $t1, 4($sp)
    sw   $t0, 0($sp)
    ### push stack ###
    l.d  $f8, ten
    l.d  $f2, zero
    l.d  $f4, one
    move $t2, $zero
    lbu  $t0, 0($a0)
    li   $t1, '-'
    bne  $t0, $t1, str_to_double.positive
    l.d  $f4, minus_one
    addi $a0, $a0, 1
    j    str_to_double.calc
str_to_double.positive:
    lbu  $t0, 0($a0)
    li   $t1, '+'
    bne  $t0, $t1, str_to_double.calc
    addi $a0, $a0, 1
str_to_double.calc:
    lbu  $t0, 0($a0)
    beq  $t0, $zero, str_to_double.done
    li   $t1, '.'
    bne  $t0, $t1, str_to_double.not_point
    li   $t2, 1
    addi $a0, $a0, 1
    j    str_to_double.calc
str_to_double.not_point:
    li   $t1, '0'
    bltu $t0, $t1, str_to_double.error
    li   $t1, '9'
    bltu $t1, $t0, str_to_double.error
    subi $t0, $t0, '0'
    beq  $t2, $zero, str_to_double.other
    div.d  $f4, $f4, $f8
str_to_double.other:
    mul.d  $f2, $f2, $f8
    mtc1   $t0, $f6
    cvt.d.w  $f6, $f6
    add.d  $f2, $f2, $f6
    addi $a0, $a0, 1
    j    str_to_double.calc
str_to_double.done:
    mul.d  $f2, $f2, $f4
str_to_double.exit:
    ### pop stack ###
    lw   $t0, 0($sp)
    lw   $t1, 4($sp)
    lw   $t2, 8($sp)
    lw   $ra, 12($sp)
    addi $sp, $sp, 16
    jr $ra
str_to_double.error:
    la   $a0, err_msg
    j    error
################################################################################
# description:
# void error(char* <a0>, char* <a1>, char* <a2>, char* <a3>)
# print error message and exit
################################################################################
error:
    beq  $a0, $zero, error.message1
    li   $v0, 4
    syscall
error.message1:
    beq  $a1, $zero, error.message2
    move $a0, $a1
    li   $v0, 4
    syscall
error.message2:
    beq  $a2, $zero, error.message3
    move $a0, $a2
    li   $v0, 4
    syscall
error.message3:
    beq  $a3, $zero, error.message4
    move $a0, $a3
    li   $v0, 4
    syscall
error.message4:
    j    exit
################################################################################
# exit()
# 
################################################################################
exit:
    li   $v0, 17  # exit
    syscall
